#include<iostream>
#include<vector>
#include<string>
#include<functional>

using namespace std;

/*分离链接散列表*/
template <typename HashedObj>
class HashTable
{

private:
    /*键值对对象的存储向量*/
    vector<list <HashedObj>> theLists;
    /*当前哈希表大小*/
    int currentSize;
    /*重建函数（再散列）*/
    void rehash()
    {   
        /*保存原哈希表（二阶向量（桶:Obj））*/
        vector<list<HashedObj> > oldLists = theLists;
        /*把桶向量变成二倍长*/
        theLists.resize(nextPrime(2 * theLists.size()));
        /*把桶向量清空*/
        for (auto & thisList : theLists)
            thisList.clear();
        
        currentSize = 0;
        /*对新哈希表赋值*/
        for (auto & thisList : oldLists)
            for (auto & x : thisList)
                insert (std::move(x));
    }
    /*哈希函数，输入键查找值*/
    size_t myHash(const HashedObj & x) const;
    {
        /*局部静态变量，可以随着运行而不断更新*/
        static hash <HashedObj> hf;
        /*映射取法是余数法*/
        return hf(x) % theLists.size(); //size是当前值的数量，capacity是桶的数量
        //()符号经过重载，用来取键值对对象x的键成员
        //()的重载定义不是泛型的，它必须在具体化中进行定义
    }

public:
    /*显式构造函数*/
    explicit HashTable(int size = 101);
    /*检测是否包含数据项*/
    bool contains (const HashedObj & x) const
    {
        /*查找数据项所对应的键*/
        auto & whichList = theLists[myHash(x)]; //哈希值就是元素在哈希表中的序号，可以直接充当索引
        /*迭代器：begin(vec) == vec.begin()*/
        return find (begin (whichList), end(whichList), x ) != end(whichList);
    }
    /*清空操作：清空键向量，则值的索引丢失*/
    void makeEmpty()
    {
        for (auto & thisList : theLists)
            thisList.clear();
    }
    /*插入项*/
    bool insert (const HashedObj & x);
    {
        /*调用contain，若找不到则在键向量的尾部添加一个值*/
        auto & whichList = theLists[myHash(x)];
        if(find(begin(whichList),end(whichList,x),x) != end(whichList) )
            return false;
        whichList.push_back(x);
        /*如果超出桶的数量，则重建一个哈希表*/
        if(++currentSize > theLists.size())
            rehash();
        /*重建成功*/
        return true;
    }
    bool insert (HashedObj && x);
    /*删除项*/
    bool remove (const HashedObj & x)
    {
        auto & whichList = theLists[myHash(x)];
        auto itr = find(begin(whichList), end(whichList),x);

        if(itr == end(whichList))
            return false;

        whichList.erase(itr);
        --currentSize;
        return true;
    }
};

/*C++11中的哈希函数对象
template <typename Key>
class hash
{
    public:
        size_t operator() (const Key& k) const;
};
// 显式具体化为字符串映射
template<>
class hash<string>
{
    public:
        size_t operator() (const string & key)
        {
            size_t hashVal = 0;
            for (char ch : key)
                hashVal = 37*hashVal + ch;
            return hashVal
        }
};
*/

/*HashedObj（键）的实例*/
class Employee
{
private:
    string name;
    double salary;
    int seniority;
public:
    const string & getName() const
        { return name; }
    /*只要Employee的name不同，则判定键不同*/
    bool operator== (const Employee & rhs) const
        { return getName() == rhs.getName(); }
    bool operator!= (const Employee & rhs) const
        { return !(*this == rhs); }
};
/*显式具体化*/
template<>
class hash<Employee>
{
public:
    /*()符号：通过键查找值*/
    size_t operator() (const Employee & item)
    {
        static hash<string> hf;
        return hf(item.getName());
    }
};